【连载】比特币史话 | 拜占庭将军(1)

(圣索菲亚大教堂，伊斯坦布尔。图片来源于网络)

本篇看点：拜占庭将军们的故事是怎样的由来？中本聪一路闯关，开始从密码学跨界进入分布式计算领域，他将面临的又是怎样一副局面呢？

前情回顾：

正文：

在今天的土耳其境内，有一个连接黑海和地中海、横跨亚洲和欧洲因而位居战略要冲的著名城市，伊斯坦布尔(Istanbul)。在罗马帝国时期，她的名字叫做君士坦丁堡(Constantinople)，并曾经一度作为东罗马帝国的首都。而在公元前658年始建之际，她的名字叫做拜占庭(Byzantine)。[公众号:刘教链]

在一次围城之战中，拜占庭帝国的将军们兵分几路，分别从不同方向向敌军进攻。将军们之间只能依靠信使传递消息，而信使则有被敌军截获、丢失消息，甚至策反、传递假消息的可能性。更糟糕的是，将军之中据信也有被敌军策反者，不仅可能拒绝呼应其他将军的行动，甚至有可能故意发出假情报，欺骗、干扰其他将军，阻止他们就作战行动达成一致。试问，在这种情况下，这些拜占庭的将军们有什么方法可以就作战计划达成一致呢？[1][公众号:刘教链]

这就是计算机分布式系统领域中著名的“拜占庭将军问题”(Byzantine Generals Problem)。这是一个故事，也是一个比喻。讲这个故事的人正是美国计算机科学家莱斯利·兰伯特(Leslie Lamport)。事实上，莱斯利·兰伯特是先论证的解决方案，然后才提出了这个问题。[公众号:刘教链]

最早意识到拜占庭共识问题的人，其实是美国计算机科学家罗伯特·肖斯塔克(Robert Shostak)。他是在1978年为美国航空航天局(NASA)资助的SIFT项目工作是发现这个问题的，并将其称为交互式一致性问题。后来，1980年4月，他和莱斯利·兰伯特一起发表了对于这个问题的研究论文，指出有算法可以在不超过1/3坏节点的情况下达成共识。但是，解法有了，问题却由于过于复杂而难以被理解。于是莱斯利·兰伯特决定讲一个好故事，以便帮助大家理解这个问题。他最初选择的故事背景发生在另一个城市，后来经别人建议才改到了拜占庭，这才有了1982年的论文《拜占庭将军问题》(The Byzantine Generals Problem)[2]。莱斯利·兰伯特在论文中所给出的解决方案，就是所谓“拜占庭容错”(BFT, Byzantine Fault Tolerant)算法。后人在其基础上，又陆续提出了很多的变种算法，比如1999年由米格尔·卡斯特罗(Miguel Castro)和巴巴拉·里斯科夫(Barbara Liskov)提出的“实用拜占庭容错算法”(PBFT)等。[公众号:刘教链]

莱斯利·兰伯特的故事深入人心。在他讲的故事里，将军就是网络节点，信使就是互联网通信，作战行动就是信息，达成共识就是每个节点都建立相同的全局观(又称全局视图，global view)；忠诚的将军就是正常工作的节点，失联的将军就是不工作的、联系不上的节点，被策反的叛徒将军就是主动作恶、作弊的节点。只能容许忠诚将军存在的网络是难以规模化的。随着互联网的发展，节点数量的增加，必然出现节点故障、将军失联的情况。我们都听说过谷歌早年用普通PC机搭建集群，通过软件实现高可用性的故事。谷歌所实现的，就是所谓“崩溃容错”(CFT, Crash Fault Tolerant)算法。如果更进一步，允许网络中出现非受控的作恶节点、叛徒将军，那么网络环境就会进一步恶化为所谓“拜占庭网络”，此时就需要所谓“拜占庭容错”(BFT)算法才能保证系统的稳定、安全运行。[公众号:刘教链]

在2008年中本聪为了发明比特币而提出工作量证明链之前，没有人知道怎么在全球互联网规模(1万至10万数据节点)上实现有效的拜占庭容错。整个互联网行业选择了另外一条技术路线，抛弃互联网创立之初的去中心化理念和构想，走向中心化控制，通过中心化控制权去识别、阻止和驱逐叛徒将军，让所有数据节点工作在一个中心化管控的、安全的环境中，从而把问题降级为更为简单的“崩溃容错”问题。但是即便如此，1985年的一篇著名论文仍然给了计算机科学家和工程师们一记重击...[公众号:刘教链]

【未完待续】(公众号：刘教链)